package leetcode101_xqzhao

// TODO 最长回文子串 【-】 中心扩散法

func longestPalindrome(s string) string {
	n, maxLen := len(s), 0
	tmpL, tmpR := 0, 0

	for i := 0; i < n; i++ {
		l1, r1 := expand(i, i, s)
		l2, r2 := expand(i, i+1, s)
		len1 := r1 - l1 + 1
		len2 := r2 - l2 + 1
		if len1 > maxLen {
			maxLen = r1 - l1 + 1
			tmpL, tmpR = l1, r1
		}
		if len2 > maxLen {
			maxLen = r2 - l2 + 1
			tmpL, tmpR = l2, r2
		}
	}
	return s[tmpL : tmpR+1]
}

func expand(left int, right int, s string) (int, int) {
	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {

	}
	return left + 1, right - 1
}
